Storage devices based on flash memories have become very attractive in recent years. For example, they are commonly used as mass memories (also known as solid-state mass memories) in data processing systems. These storage devices are compact, robust and have low power consumption. Therefore, they are advantageous especially in portable systems (such as mobile telephones), which are typically supplied by batteries.
Each flash memory used to implement the above-mentioned storage devices can be erased only in blocks having a relatively large size (for example, 16-128 Kbytes). Therefore, once data has been written into the flash memory, this data cannot be updated any longer (unless the corresponding whole block is erased). In order to emulate operation of a random access device (such as in standard hard-disks), a translation layer is provided on top of the flash memory. The translation layer manages any update of the data stored in the flash memory by writing a new version thereof in a different area of the flash memory (at the same time updating corresponding mapping information).
A problem of the flash memory is that some of its blocks may be defective (or bad), and then unusable. Typically, the bad blocks are detected in a factory (before shipping the storage device) during a corresponding test process—such as of the Electrical-Wafer Sorting (EWS) type. Moreover, the bad blocks may appear in the field (during operation of the storage device). For example, this happens when the erasure of a block fails (because of an excessive wearing of its memory cells, which endurance to the erasures is intrinsically limited).
In order to alleviate this problem, it has been proposed to skip any bad block and to replace it with a next one in the flash memory that is good (i.e., available to be used). The technique is well suited to a sequential use of the storage device; however, it is very difficult to apply when the storage device must support a random access.
Another approach that has been used consists of providing a set of spare (or redundancy) blocks, which are reserved for replacing the bad blocks. The bad blocks are then mapped on the corresponding spare blocks by means of a replacement table (for example, of the associative type). Particularly, for each bad block the replacement table stores an indication of the spare block to be used in substitution of the bad block. Before performing any operation on a current block of the flash memory, an entry in the replacement table for the current block is searched. If the entry is not found, the operation is performed on the (good) current block. Conversely, the operation is performed on the spare block associated with the (bad) current block in the replacement table.
A drawback of the solution described above is that it involves a large waste of area of the flash memory for implementing the spare blocks. Indeed, the spare blocks are used only when they must replace corresponding bad blocks. Otherwise, the spare blocks are completely useless. As a result, the number of spare blocks is generally maintained relatively low (for example, several units). However, this strongly reduces the capability of ensuring the correct operation of the flash memory with a high number of bad blocks.
Moreover, every operation on the flash memory requires the above-mentioned search in the replacement table (for a possible spare block associated therewith). Therefore, this adversely affects an access time of the storage device.
In this respect, it should be noted that the time that is spent to search an entry for the current block in the replacement table depends on its size. This further limits the number of spare blocks that can be provided. The problem is particularly acute when the flash memory has a very large size. Indeed, the overhead in the access time increases with the number of the spare blocks, so that it must be kept low in absolute terms to ensure an acceptable access time. Therefore, the number of spare blocks decreases in relative terms as the size of the flash memory increases.